package algo;

import model.tsp.Problem;
import model.tsp.Solution;

import java.util.LinkedList;
import java.util.List;

public class TabuSearch extends LocalSearch {

    private LinkedList<Integer> tabuList = new LinkedList<>();


    public TabuSearch(Problem problem) {
        super(problem);
    }

    @Override
    protected Solution improve(Solution solution) {
        Solution bestSolution = solution.copy();
        int epochs = 3000;
        for (int epoch = 0; epoch < epochs; epoch++) {
            System.out.println("epoch:" + epoch);
            Solution localBestSolution = tabuLocalSearch(solution);
            int hashCode = localBestSolution.hashCode();
            // 更新禁忌表
            updateTabuList(hashCode);
            if (localBestSolution.getCost() < bestSolution.getCost()) {
                bestSolution = localBestSolution.copy();
            }
        }
        return bestSolution;
    }

    private Solution tabuLocalSearch(Solution solution) {
        Solution currentSolution = solution.copy();

        int k = 1;
        int kMax = 6;
        int localSearchCnt = 3000;
        while (k <= kMax) {
            System.out.println("Neighborhood:" + k);
            // 局部搜索过程，搜索邻域k中的较优解
            // 每个操作算子随机变换一次
            for (int i = 0; i < localSearchCnt; i++) {
                List<Integer> newX;
                if (k == 1) {
                    newX = neighborhoodOperator1(currentSolution.getPermutation());
                } else if (k == 2) {
                    newX = neighborhoodOperator2(currentSolution.getPermutation());
                } else if (k == 3) {
                    newX = neighborhoodOperator3(currentSolution.getPermutation());
                } else if (k == 4) {
                    newX = neighborhoodOperator4(currentSolution.getPermutation());
                } else if (k == 5) {
                    newX = neighborhoodOperator5(currentSolution.getPermutation());
                } else if (k == 6) {
                    newX = neighborhoodOperator6(currentSolution.getPermutation());
                } else {
                    throw new RuntimeException("超出neighborhood邻域集合长度: " + k);
                }

                Solution newSolution = new Solution(newX, calculateFitness(newX));

                if (!isInTabuList(newSolution.hashCode())) {
                    if (newSolution.getCost() < currentSolution.getCost()) {
                        currentSolution = newSolution.copy();
                        System.out.format("第%d次迭代当前最优解:%d\n", i + k * localSearchCnt, currentSolution.getCost());
                    }
                }
            }

            k++;
        }
        return currentSolution;
    }

    // 将解向量的hash值加入禁忌表
    private void updateTabuList(int hashValue) {
        int tabuLen = 10;
        // 如果超出禁忌表长度
        if (tabuList.size() == tabuLen) {
            tabuList.removeFirst();
        }
        tabuList.add(hashValue);
    }

    // 判断解向量的hash值是否在禁忌表中
    private boolean isInTabuList(int hashValue) {
        for (int tabuHashValue : tabuList) {
            if (tabuHashValue == hashValue) {
                return true;
            }
        }
        return false;
    }
}
